﻿import { Rectangle } from "common/geom";

type PackResult = {
    width: number,
    height: number,
    rectangles: Rectangle[],
    rotates?: Rectangle[]
}

function getNextHighestPOT(value: number): number {
    // v & v - 1
    // v && !(v & (v - 1))
    // v & v - 1? 1 << v.toString(2).length: v
    if (value > 1) {
        value--;
        value |= value >> 1;
        value |= value >> 2;
        value |= value >> 4;
        value |= value >> 8;
        value |= value >> 16;
        value++;
    }
    else {
        value = 2;
    }

    return value;
}

function sortRectangles(rectA: Rectangle, rectB: Rectangle): number {
    const vA = rectA.width + rectA.height;
    const vB = rectB.width + rectB.height;
    if (vA === vB) {
        return rectA.width > rectB.width ? -1 : 1;
    }

    return vA > vB ? -1 : 1;
}

export default class BoxPacker {
    public borderPadding: number = 2;
    public shapePadding: number = 2;
    public maxWidth: number = 2048;
    public maxHeight: number = 2048;
    public potSize: boolean = false;
    public allowRotate: boolean = false;

    private _width: number = 0;
    private _height: number = 0;
    private _rotates: Rectangle[] = [];
    private _rectanglesPacked: Rectangle[];
    private _rotatesPacked: Rectangle[];

    public constructor() {
    }

    public pack(rectangles: Rectangle[]): PackResult[] {
        rectangles = rectangles.concat();
        this.maxWidth = Math.ceil(this.maxWidth);
        this.maxHeight = Math.ceil(this.maxHeight);
        this.borderPadding = Math.ceil(this.borderPadding);
        this.shapePadding = Math.ceil(this.shapePadding);
        this._rotates.length = 0;

        // Rotate rectangle, ceil size.
        for (let i = 0, l = rectangles.length; i < l; ++i) {
            const rectangle = rectangles[i];
            const width = Math.ceil(rectangle.width);
            const height = Math.ceil(rectangle.height);
            rectangle.width = width;
            rectangle.height = height;
            if (this.allowRotate && height > width) { // 支持旋转，宽高对调，装箱后复原。
                rectangle.width = height;
                rectangle.height = width;
                this._rotates.push(rectangle);
            }
        }

        const results: PackResult[] = [];
        while (rectangles.length > 0) {
            if (this._packEach(rectangles)) {
                const result: PackResult = {
                    width: this._width,
                    height: this._height,
                    rectangles: this._rectanglesPacked
                };
                if (this._rotatesPacked.length > 0) {
                    result.rotates = this._rotatesPacked;
                }
                results.push(result);
            }
            else {
                break;
            }
        }

        return results;
    }

    private _packEach(rectangles: Rectangle[]): boolean {
        // 预估总面积。
        this._width = 0;
        this._height = 0;
        let totalSurfaceArea = 0;
        for (let i = 0, l = rectangles.length; i < l; ++i) {
            const rectangle = rectangles[i];
            totalSurfaceArea += (rectangle.width + this.shapePadding) * (rectangle.height + this.shapePadding);
            this._width = Math.max(rectangle.width + this.shapePadding, this._width);
            this._height = Math.max(rectangle.height + this.shapePadding, this._height);
        }
        totalSurfaceArea += totalSurfaceArea * 0.3;
        console.assert(totalSurfaceArea > 0);
        // 按照面积降序排序。
        rectangles.sort(sortRectangles);
        // 预估总箱宽高。（不算边框）
        if (this.potSize) {
            this._width = Math.max(this._width, getNextHighestPOT(Math.ceil(Math.sqrt(totalSurfaceArea)) + this.borderPadding * 2) - this.borderPadding * 2);
            this._width = Math.min(this._width, Math.max(getNextHighestPOT(this.maxWidth) - this.borderPadding * 2, 0));
        }
        else {
            this._width = Math.min(Math.max(this._width, Math.ceil(Math.sqrt(totalSurfaceArea))), Math.max(this.maxWidth - this.borderPadding * 2, 0));
        }
        this._height = Math.max(this._height, this.maxHeight - this.borderPadding * 2);
        console.assert(this._width * this._height > 0);

        this._rectanglesPacked = [];
        this._rotatesPacked = [];
        const boxes: Rectangle[] = [new Rectangle(0, 0, this._width, this._height)];
        this._width = 0;
        this._height = 0;

        while (rectangles.length > 0) {
            let rectangleWidth = 0;
            let rectangleHeight = 0;
            let boxIndex = -1;
            let box: Rectangle | null = null;
            for (let i = 0, l = boxes.length; i < l; ++i) { // 找到最高位的箱子。
                const eachBox = boxes[i];
                if (eachBox.height >= rectangleHeight) {
                    rectangleHeight = eachBox.height;
                    boxIndex = i;
                    box = eachBox;
                }
            }

            if (box === null) {
                break;
            }

            // 尝试装箱。
            let rectangleIndex = -1;
            let rectangle: Rectangle | null = null;
            for (let i = 0, l = rectangles.length; i < l; ++i) {
                rectangle = rectangles[i];
                if (rectangle.width * rectangle.height <= 0) { // 过滤非法的数据。
                    continue;
                }

                rectangleWidth = rectangle.width + this.shapePadding;
                rectangleHeight = rectangle.height + this.shapePadding;
                if (box.width >= rectangleWidth && box.height >= rectangleHeight) {
                    rectangleIndex = i;
                    break;
                }
            }

            // 没有合法数据。
            if (rectangle === null) {
                break;
            }

            if (rectangleIndex >= 0) {
                // 更新总箱宽高。
                this._width = Math.max(this._width, box.x + rectangle.width);
                this._height = Math.max(this._height, box.y + rectangle.height);

                // 装箱。
                rectangle.x = box.x + this.borderPadding;
                rectangle.y = box.y + this.borderPadding;
                rectangles.splice(rectangleIndex, 1);
                this._rectanglesPacked.push(rectangle);
                if (this._rotates.indexOf(rectangle) > 0) { // 旋转的复原。
                    const width = rectangle.width;
                    rectangle.width = rectangle.height;
                    rectangle.height = width;
                    this._rotatesPacked.push(rectangle);
                }

                // 合并箱子。
                const isFitWidth = rectangleWidth === box.width;
                const isFitHeight = rectangleHeight === box.height;
                if (isFitWidth && isFitHeight) { // 宽高都合适。
                    boxes.splice(boxIndex, 1);
                }
                else if (isFitWidth) { // 宽度合适。
                    box.y += rectangleHeight;
                    box.height -= rectangleHeight;
                }
                else if (isFitHeight) { // 高度合适。
                    box.x += rectangleWidth;
                    box.width -= rectangleWidth;
                }
                else { // 宽高都大。
                    const newBox: Rectangle = new Rectangle();
                    newBox.copyFrom(box);
                    newBox.x += rectangleWidth;
                    newBox.width -= rectangleWidth;

                    box.y += rectangleHeight;
                    box.width = rectangleWidth;
                    box.height -= rectangleHeight;

                    boxes.splice(boxIndex + 1, 0, newBox);
                }
            }
            else if (boxes.length > 1) {
                // 没有一个能放下的，将相邻的箱子合并，再试一次。
                let rectangleFreePrev: Rectangle;
                let rectangleFreeNext: Rectangle;
                if (boxIndex === 0) {
                    rectangleFreeNext = boxes[boxIndex + 1];
                }
                else if (boxIndex === boxes.length - 1) {
                    rectangleFreeNext = boxes[boxIndex - 1];
                }
                else {
                    rectangleFreePrev = boxes[boxIndex - 1];
                    rectangleFreeNext = boxes[boxIndex + 1];
                    if (rectangleFreePrev.height === rectangleFreeNext.height) {
                        box.width += rectangleFreeNext.width;
                        boxes.splice(boxIndex + 1, 1);
                        rectangleFreeNext = rectangleFreePrev;
                    }
                    else if (rectangleFreePrev.height >= rectangleFreeNext.height) {
                        rectangleFreeNext = rectangleFreePrev;
                    }
                }

                // 合并水平箱位。
                if (box.x < rectangleFreeNext.x) {
                    rectangleFreeNext.x = box.x;
                }
                rectangleFreeNext.width += box.width;
                boxes.splice(boxIndex, 1);
            }
            else { // 再也没有合适的剩余箱位。
                break;
            }
        }

        if (this._rectanglesPacked.length > 0) { // 至少放了一个，则更新总箱宽高。
            this._width += this.borderPadding * 2;
            this._height += this.borderPadding * 2;

            if (this.potSize) {
                this._width = getNextHighestPOT(this._width);
                this._height = getNextHighestPOT(this._height);
            }
            else { // 总箱的宽高应为偶数。
                if (this._width % 2) {
                    this._width++;
                }

                if (this._height % 2) {
                    this._height++;
                }
            }

            return true;
        }

        return false;
    }
}